package sjg.DataStructures.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * 基数排序
 * 步骤： 1. 取个位，放入对应的桶中 2. 取十位，放入对应的桶中 3. 取百位放到对应桶中
 */
public class RadixSort {
    public static void main(String[] args) {

        // int[] arr = {53, 3, 542, 748, 14, 214};
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0,8000000)数
        }

        // System.out.println("排序前：");
        // SortUtils.print(arr);

        Date date_begin = new Date();
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String beginDate = sdf.format(date_begin);
        System.out.println("排序前的时间是=" + beginDate);
        radixSort(arr);

        Date date_over = new Date();
        String overDate = sdf.format(date_over);
        System.out.println("排序后的时间是=" + overDate);

        // System.out.println("排序后：");
        // SortUtils.print(arr);
    }

    private static void radixSort(int[] arr) {
        // 获取数组中最大的位数
        int max = arr[0]; // 假设是第一位最大
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 得到最大是几位数
        int maxLength = (max + "").length();

        // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        // 1. 二维数组包含10个一维数组
        // 2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定位arr.length
        // 基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];

        // 为了记录每个桶中，实际存放了多少个数据，定义一个一维数组来记录各个桶的每次放入的数据个数
        // 可以这样理解：比如：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        // 使用循环处理
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            // 针对每个元素的对应位进行排序处理，第一次是个位...
            for (int j = 0; j < arr.length; j++) {
                // 取出每个元素的对应位的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }

            // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            // 遍历每一桶，并将桶中的数据，放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中，有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    // 循环该桶即第k个桶(即第k个一维数组)，放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        // 取出元素放入到arr
                        arr[index++] = bucket[k][l];
                    }
                }
                // 第i+1轮处理后，需要将每个bucketElementCounts[k] = 0
                bucketElementCounts[k] = 0;

            }

            // System.out.println("第"+(i+1)+"轮，对各位的排序处理 arr = "+ Arrays.toString(arr));
        }

    }
}
